Signature Scheme utilising Hash functions.

It’s stateful, meaning the verifier and the signer have to keep track of some state.

Standardisation

• IETF RFC in 2018
• NIST Standard with LMS (similar scheme)
• ISO Standard

Lamport Signature Scheme

They use the Winternitz Checksum which is $c=\sum_{i=1}^{n}{w-m_i}$ Which is then encoded in base $w$. This can be used for the Winternitz One-time Signature Scheme. This is the base for XMSS, which turns the one-time signature scheme into a few-time signature scheme.

Problem - each of these keys can only be used once. So how do we generate a bunch of keys? Verifier can verify a given public key with only one hash per level of the tree.

The state is needed so the verifier knows which public key is being used at a given time.